package com.gy.algorithm.carl.strexa;

/**
 * @BelongsProject: javabase
 * @BelongsPackage: com.gy.algorithm.carl
 * @Author: gy
 * @Date: 2024/10/22 11:30
 * @Description:
 */
public class ReverseWords151 {

    public static void main(String[] args) {
        String theSkyIsBlue = reverseWords("the sky is blue");
        System.out.println(theSkyIsBlue);
    }

    // end
    public static String reverseWords(String s) {
        char[] arr = s.toCharArray();

        // 通过快慢指针把空格处理了
        int slow = 0;
        int fast = 0;
        for (;fast < arr.length;fast++){
            if(arr[fast] != ' '){
                // 首位不加空格 其他位置单词前先加一个空格
                if(slow != 0){
                    arr[slow++] = ' ';
                }
                while(fast < arr.length && arr[fast] != ' '){
                    arr[slow++] = arr[fast++];
                }
            }
        }
        char[] newArrs = new char[slow];
        System.arraycopy(arr,0,newArrs,0,slow);
        arr = newArrs;

        // 整体翻转
        reverseWords(arr,0,arr.length - 1);

        // 每个单词翻转
        int start = 0;
        int end = 0;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] != ' ') {
                end++;
                continue;
            }
            reverseWords(arr,start,end - 1);
            end = end + 1;
            start = end;
        }
        reverseWords(arr,start,end - 1);

        return new String(arr);
    }

    private static void reverseWords(char[] arr,int start ,int end) {
        while(start < end){
            arr[start] ^= arr[end];
            arr[end] ^= arr[start];
            arr[start] ^= arr[end];

            start++;
            end--;
        }
    }

    private static void reverseWords1(char[] arr,int start ,int end) {
        while(start < end){
            char temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;

            start++;
            end--;
        }
    }

    // write
    public static String reverseWords1(String s) {
        StringBuilder res = new StringBuilder();
        char[] arr = s.toCharArray();
        int start = Integer.MIN_VALUE;
        int end = Integer.MIN_VALUE;

        for (int i = arr.length - 1; i >= 0; i--) {
            if (arr[i] == ' ') continue;

            // 找单词范围
            start = i;
            while (i > 0 && arr[i] != ' ') i--;

            if (i == 0) {
                if (arr[i] != ' ') {
                    end = 0;
                } else {
                    end = i + 1;
                }
            } else {
                end = i + 1;
            }

            // 组装单词
            for (int j = end; j <= start; j++) {
                res.append(arr[j]);
            }
            res.append(" ");
        }

        res.deleteCharAt(res.length() - 1);

        return res.toString();
    }
}
